package gold.digger;

import gold.utils.InputUtil;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC967 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        List<Integer> ans = new ArrayList<>();
        int n = 0, k = 0;

        public int[] numsSameConsecDiff(int nn, int kk) {
            n = nn;
            k = kk;
            backTrace(new StringBuilder(), 0);

            int[] res = new int[ans.size()];
            for (int i = 0; i < ans.size(); i++) res[i] = ans.get(i);
            return res;
        }

        public void backTrace(StringBuilder cur, int curPos) {
            if (curPos >= n) {
                ans.add(Integer.parseInt(cur.toString()));
                return;
            }

            if (cur.length() <= 0) {
                for (int i = 1; i <= 9; i++) subTrace(cur, curPos, i);
            } else {
                // 需要考虑前面的数字
                int prev = cur.charAt(curPos - 1) - '0';
                if (prev + k <= 9 && prev + k >= 0) subTrace(cur, curPos, prev + k);
                if (k > 0 && prev - k <= 9 && prev - k >= 0) subTrace(cur, curPos, prev - k);
            }
        }

        public void subTrace(StringBuilder cur, int curPos, int num) {
            cur.append(String.valueOf(num));
            backTrace(cur, curPos + 1);
            cur.deleteCharAt(curPos);
        }
    }

    public void run() {
        Solution solution = new Solution();
        System.out.println(Arrays.toString(solution.numsSameConsecDiff(3, 7))); //[181,292,707,818,929]
//        System.out.println(Arrays.toString(solution.numsSameConsecDiff(2, 1))); //[10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]
//        System.out.println(Arrays.toString(solution.numsSameConsecDiff(2, 2))); //[13,20,24,31,35,42,46,53,57,64,68,75,79,86,97]
//        System.out.println(Arrays.toString(solution.numsSameConsecDiff(2, 0))); //[11, 22, 33, 44, 55, 66, 77, 88, 99]
    }

    public static void main(String[] args) throws Exception {
        LC967 an = new LC967();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
